/*
1770. 执行乘法运算的最大分数  https://leetcode.cn/problems/maximum-score-from-performing-multiplication-operations/
困难 通过 2024/11/18
思路：我使用了动态规划，通过构建一个一维数组`dp`来存储在每一步操作后的最大分数。`dp[i]`表示在执行了`i`步操作后能够得到的最大分数。代码从最后一步开始向前模拟每一步操作，每一步都考虑从左侧或右侧选择一个元素，并更新`dp`数组。最终，`dp[0]`存储了在执行完所有操作后能得到的最大分数。
*/
#include<iostream>
#include<vector>
#include<algorithm> 
using namespace std;

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int n = nums.size();
        int m = multipliers.size();
        
        // dp[i] 表示在第 i 步时的最大分数，表示从左端选取 i 个元素，剩余选择从右端
        vector<int> dp(m + 1, 0);
        
        // 从右到左考虑每个步数
        for (int i = m - 1; i >= 0; --i) {
            vector<int> temp(m + 1, 0);
            
            for (int j = 0; j <= i; ++j) {
                int left = j;
                int right = i - j;
                temp[j] = max(dp[j + 1] + nums[left] * multipliers[i],
                             dp[j] + nums[n - 1 - right] * multipliers[i]);
            }
            
            dp = move(temp);
        }

        return dp[0];
    }
};

int main() {
    Solution solution;
    vector<int> nums = {1, 2, 3};
    vector<int> multipliers = {3, 2, 1};
    int result = solution.maximumScore(nums, multipliers);
    cout << "最大分数为: " << result << endl; // 这里应该输出 14
    return 0;
}